package 树与图.字典树;

import java.util.Stack;

/**
 * 98. 验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 有效 二叉搜索树定义如下：
 * 节点的左
 * 子树
 * 只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 思路： 继续采用中序遍历，中序遍历二叉搜索树，得到升序序列，然后判断相邻节点是否递增即可
 *  定义一个前驱节点去比较
 *
 *  正确解题思路
 * 二叉搜索树的特征是：中序遍历结果为严格递增序列，且每个节点的值必须严格大于左子树所有节点，严格小于右子树所有节点。验证方法如下：
 * 中序遍历：利用中序遍历的升序特性。
 * 维护前驱节点值：记录遍历过程中上一个节点的值 pre，确保当前节点值 > pre。
 * 递归或迭代实现：通过递归或显式栈完成中序遍历，及时终止无效情况。
 */
public class L_98 {

    private Integer pre=null;

    public boolean isValidBST(TreeNode root) {
        return inOrder(root);
    }

    private boolean inOrder(TreeNode node){
        // 空节点默认视为合法
        if(node == null){
            return true;
        }
        // 检测左子树是否合法，因为空节点默认合法，所以递归条件要判断false的情况
        if(!inOrder(node.left)){
            return false;
        }
        if(pre != null && pre >= node.val){
            return false;
        }
        // 更新前驱节点
        pre = node.val;
        return inOrder(node.right);
    }

    /**
     * 迭代实现的逻辑
     * @param root
     * @return
     */
    public boolean isValidBST111(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        Integer pre = null;

        while (curr != null || !stack.isEmpty()) {
            // 遍历到最左节点
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();

            // 检查当前节点是否合法
            if (pre != null && curr.val <= pre) {
                return false;
            }
            pre = curr.val;

            // 转向右子树
            curr = curr.right;
        }
        return true;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
